package algocasts;

public class P107_JumpGameII {
    public int jump(int[] nums) {
        int n = nums.length, max = 0;
        int[] d = new int[n];
        for (int i = 0; i < n; i++) {
            if (max >= n - 1) return d[n - 1];
            if (i > max) return -1;
            max = Math.max(max, i + nums[i]);
            int last = Math.min(max, n - 1);
            for (int j = last; j > i && d[j] == 0; j--)
                d[j] = d[i] + 1;
        }
        return -1;
    }

    public int jumpO1(int[] nums) {
        if (nums.length == 1) return 0;
        int n = nums.length, max = 0, jumps = 0, curEnd = 0;
        for (int i = 0; i < n; i++) {
            if (max >= n - 1) return jumps + 1;
            if (i > max) return -1;
            if (i > curEnd) {
                ++jumps;
                curEnd = max;
            }
            max = Math.max(max, nums[i] + i);
        }
        return -1;
    }
}
